package dp

import "math"

func coinChange(coins []int, amount int) int {
	// f(i) 定义为组成金额i最少的硬币数量
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = math.MaxInt32
	}
	dp[0] = 0
	for i := 0; i < len(dp); i++ {
		for _, coin := range coins {
			if i - coin < 0 {
				continue
			}
			dp[i] = min(dp[i], 1 + dp[i - coin])
		}
	}
	if dp[amount] == math.MaxInt32 {
		return -1
	}
	return dp[amount]
}